package leetcode101.double_pointer;

/**
 * @author Synhard
 * @version 1.0
 * @Class leetcode101.graph.Code1
 * @Description Linked List Cycle II(Medium)
 * Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
 *
 * There is a cycle in a linked list if there is some node
 * in the list that can be reached again by continuously following the next pointer. 
 * Internally, pos is used to denote the index of the node that tail's next pointer is connected to.
 * Note that pos is not passed as a parameter.
 *
 * Notice that you should not modify the linked list.
 *
 *
 * Example 1:
 *
 *
 * Input: head = [3,2,0,-4], pos = 1
 * Output: tail connects to node index 1
 * Explanation: There is a cycle in the linked list, where tail connects to the second node.
 * Example 2:
 *
 *
 * Input: head = [1,2], pos = 0
 * Output: tail connects to node index 0
 * Explanation: There is a cycle in the linked list, where tail connects to the first node.
 * Example 3:
 *
 *
 * Input: head = [1], pos = -1
 * Output: no cycle
 * Explanation: There is no cycle in the linked list.
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-03-26 18:35
 */
public class Code1 {

    static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            this.val = x;
            next = null;
        }
    }

    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null || (head.next.next == null)) {
            return null;
        }

        ListNode slow = head, fast = head;

        do {
            fast = fast.next != null ? fast.next.next : null;
            slow = fast != null ? slow.next : null;
        } while (slow != fast);

        if (fast == null) {
            return null;
        }

        slow = head;

        while (slow != fast)
        {
            slow = slow.next;
            fast = fast.next;
        }

        return fast;
    }
}
